package unl.cse.graphs;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.jgrapht.UndirectedGraph;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.SimpleGraph;

//import unl.cse.counting.LexicoPermutation;
//import unl.cse.counting.Permutation;

public class GraphUtils{

	

	

	/**
	 * Returns true if and only if the two graphs are isomorphic; false otherwise
	 * @param a
	 * @param b
	 * @return
	 */
	public static boolean isomorphic(UndirectedGraph<String, DefaultEdge> a, UndirectedGraph<String, DefaultEdge> b) {
		
		return (getIsomorphicMap(a, b) != null);
	}
	
	/**
	 * If the given graphs are isomorphic, returns a map between the vertex sets witnessing the isomorphism.  If 
	 * the given graphs are not isomorphic, returns null.
	 * @param a
	 * @param b
	 * @return
	 */
	public static Map<String, String> getIsomorphicMap(UndirectedGraph<String, DefaultEdge> a, UndirectedGraph<String, DefaultEdge> b) {
		//TODO: implement
		
		if(a.vertexSet().size()!=(b.vertexSet().size()) || a.vertexSet().size() == 0) 
			return null;

		if(a.edgeSet().size() != b.edgeSet().size()) 
			return null;
		
		//list storing the set of vertices for G a and G b
		List<String> vertex_a_List = new ArrayList<String>(a.vertexSet());
		List<String> vertex_b_List = new ArrayList<String>(b.vertexSet());
		
		
		//get the permutation based on the number of the vertices for the second graph
		JohnsonTrotter permutate = new JohnsonTrotter();
		
		
		permutate.initialize(b.vertexSet().size());
		
		
		//Check initial permutation
		List<Element> vertex_b_perm_init = permutate.getPermutation();
		
		Map<String, String> map = new HashMap<String, String>();
		
		for(DefaultEdge pair: a.edgeSet()){
			
			//get the index based on the edge which is comprised of  a source node and  a target node on G a
			int i = vertex_a_List.indexOf(a.getEdgeSource(pair));
			int j = vertex_a_List.indexOf(a.getEdgeTarget(pair));
			
			//get the index of G b which G a's index points
			int b_u_index = vertex_b_perm_init.get(i).getValue();
			int b_v_index = vertex_b_perm_init.get(j).getValue();
			
			
			//get the G b's nodes based on their index pointed by G a's index
			String b_u = vertex_b_List.get(b_u_index);
			String b_v = vertex_b_List.get(b_v_index);
			
			//bijection
			if(b.containsEdge(b_u, b_v)){
				map.put(a.getEdgeSource(pair), b_u);
				map.put(a.getEdgeTarget(pair), b_v);
			}else{
				map.clear();
				break;
			}
			
		}
		
		if(map.size() == a.vertexSet().size()){
			return map;
		}
		else{
			map.clear();
		}
		
		
		
		while(permutate.generatePermutation()){
			List<Element> vertex_b_perm = permutate.getPermutation();
			
			
			
			for(DefaultEdge pair: a.edgeSet()){
				
				//get the index based on the edge which is comprised of  a source node and  a target node on G a
				int i = vertex_a_List.indexOf(a.getEdgeSource(pair));
				int j = vertex_a_List.indexOf(a.getEdgeTarget(pair));
				
				//get the index of G b which G a's index points
				int b_u_index = vertex_b_perm.get(i).getValue();
				int b_v_index = vertex_b_perm.get(j).getValue();
				
				
				//get the G b's nodes based on their index pointed by G a's index
				String b_u = vertex_b_List.get(b_u_index);
				String b_v = vertex_b_List.get(b_v_index);
				
				//bijection
				if(b.containsEdge(b_u, b_v)){
					map.put(a.getEdgeSource(pair), b_u);
					map.put(a.getEdgeTarget(pair), b_v);
				}
				else{
					map.clear();
					break;
				}
				
			}
			
			if(map.size() == a.vertexSet().size()){
				return map;
			}
			else{
				map.clear();
			}
		}
		
		
		return null;
	
	}
	
	public static List<String> convertToString(List<Integer> permutation) {
		
		List<String> permutation_String = new ArrayList<String>();
		
		for(Integer perm: permutation){
			permutation_String.add(String.valueOf(perm));
		}
		return permutation_String;
	}

	public static boolean equal(UndirectedGraph<String, DefaultEdge> a, UndirectedGraph<String, DefaultEdge> b) {
		
		if(!a.vertexSet().equals(b.vertexSet())) 
			return false;

		if(a.edgeSet().size() != b.edgeSet().size()) 
			return false;
		
		for(DefaultEdge e : a.edgeSet()) {
			if(b.getEdge(a.getEdgeSource(e), a.getEdgeTarget(e)) == null)
				return false;
		}

		return true;
	}
	
	public static void main(String[] args){
		UndirectedGraph<String, DefaultEdge> g1 =
	            new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);

		UndirectedGraph<String, DefaultEdge> g2 =
	            new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);

			String v_a_1 = "v1";
	        String v_a_2 = "v2";
//	        String v_a_3 = "v3";
//	        String v_a_4 = "v4";
	        
	        String v_b_1 = "a";
	        String v_b_2 = "b";
//	        String v_b_3 = "c";
//	        String v_b_4 = "d";
	        
	        // add the vertices
	        g1.addVertex(v_a_1);
	        g1.addVertex(v_a_2);
//	        g1.addVertex(v_a_3);
//	        g1.addVertex(v_a_4);
	        
	        g2.addVertex(v_b_1);
	        g2.addVertex(v_b_2);
//	        g2.addVertex(v_b_3);
//	        g2.addVertex(v_b_4);
	        
	        
	     // add edges to create a circuit
	        g1.addEdge(v_a_1, v_a_2);
//	        g1.addEdge(v_a_2, v_a_3);
//	        g1.addEdge(v_a_3, v_a_4);
//	        g1.addEdge(v_a_4, v_a_1);
	        
//	        g2.addEdge(v_b_1, v_b_3);
	        g2.addEdge(v_b_1, v_b_2);
//	        g2.addEdge(v_b_4, v_b_2);
//	        g2.addEdge(v_b_4, v_b_3);
	        
	        System.out.println("g1 = "+g1);
	        System.out.println("g2 = "+g2);
	        
	        System.out.println(GraphUtils.getIsomorphicMap(g1, g2));
	        System.out.println(GraphUtils.isomorphic(g1, g2));
	        
	        
	        
	}
}
